/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function(s, wordDict) {
    const res = []
    let path = []
    const dfs = function(str) {
        // 字符串能够被拆分完，最后一定剩下空串
        if(str === "") {
            res.push(path.join(" "))
            return
        }
        for(let i = 0; i < wordDict.length; i++) {
            // 如果字典元素不在当前第一个位置，则跳过，继续下一次循环
            if(str.indexOf(wordDict[i]) !== 0) continue
            // 是开头
            if(str.indexOf(wordDict[i]) === 0) {
                // 添加到路径中
                path.push(wordDict[i])
                // 用截取的字符串继续递归
                dfs(str.substring(wordDict[i].length))
                // 恢复路径
                path.pop(wordDict[i])
            }
        }
    }
    dfs(s)
    return res
};